/*
 * @lc app=leetcode.cn id=1819 lang=cpp
 *
 * [1819] 序列中不同最大公约数的数目
 */

// @lc code=start
class Solution
{
public:
    int countDifferentSubsequenceGCDs(vector<int> &nums)
    {
        int hash[200001] = {0}, maxNum = 0;
        for (int x : nums)
        {
            maxNum = max(maxNum, x);
            hash[x]++;
        }

        int ans = 0;
        for (int i = 1; i <= maxNum; i++)
        {
            int num = -1;
            for (int j = i; j <= maxNum; j += i)
            {
                // 如果hash[j]为0，说明j不在序列中，不用计算
                if (hash[j] == 0)
                {
                    continue;
                }
                // 计算序列里的最大公约数
                if (num == -1)
                {
                    num = j;
                }
                else
                {
                    num = gcd(num, j);
                }
            }

            if (num == i)
            {
                ans++;
            }
        }

        return ans;
    }
};
// @lc code=end
